package top;

/**
 * @author chenyw
 * @date 2022/7/13 12:56
 * @description 轮转数组
// *        方法一：环装替换   an = bk,  a为b，k的最小公倍数
// *            从远点出发，回到原点是可能是出现了循环，并没有将数组遍历完，会遍历lcm（n，k）个元素，
                所以一公会遍历n/(lcm（n，k）/k)趟，即n，k的最大公约数
                此方法最大公约数的求法没看太懂
        方法二：翻转数组
 *
 *
 */
public class Top189rotate {
    // 环状替换
//    public void rotate(int[] nums, int k) {
//        int n = nums.length;
//        k = k % n;
//        int count = gcd(k,n);
//        for (int start = 0; start < count; start++) {
//            int current = start;
//            int prev = nums[start];
//            do {
//                int next = (current + k) % n;
//                int temp = nums[next];
//                nums[next] = prev;
//                prev = temp;
//                current = next;
//            } while (start != current);
//        }
//
//    }
//
//    //x，y的最大公约数
//    private int gcd(int x, int y) {
//        return y > 0 ? gcd(y, x % y) : x;
//    }

    //翻转数组
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(0, n - 1, nums);
        reverse(0, k - 1, nums);
        reverse(k, n - 1, nums);
    }

    private void reverse(int start, int end, int[] nums) {
        while (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start += 1;
            end -= 1;
        }
    }
}
